package 力扣;

/**
 * @author yyq
 * @create 2022-03-26 21:02
 */
public class leetcode459 {
    public static void main(String[] args) {
        System.out.println(repeatedSubstringPattern("babbab"));
    }
    public static boolean repeatedSubstringPattern(String s) {
        if(s.length()==1) return true;
        // 1.初始化
        int j = 0; //前缀指针
        int i = 1; //后缀指针
        int[] next=new int[s.length()];
        char[] chars = s.toCharArray();
        // 开始逐步求出每个子串 chars[0 - i] 的最大相等前后缀的长度
        while (i<chars.length){
            // 前后缀指针值相等
            if(chars[j] == chars[i]){
                // 子串chars[0 - i] 的最大相等前后缀的长度 为前缀长度
                next[i] = j + 1;
                i++;
                j++;
            }
            // 前后缀指针值不相等
            else {
                // **** j $%&^( ****i
                // 此时需要回退 j
                while (j!=0&&chars[j]!=chars[i]){
                    j=next[j-1];
                }
                if(j==0){
                    if(chars[j]==chars[i]){
                        next[i]=1;
                        j++;
                        i++;
                    }else {
                        next[i]=0;
                        i++;
                    }
                }else {
                    next[i] = j + 1;
                    j++;
                    i++;
                }
            }
        }
        int l=next[chars.length-1];

        // 如果该字符串没有前后缀相等 肯定不是由子串组成了
        if(l==0) return false;
        for (int a = l;a<chars.length;a++){
            if(chars[a]!=chars[a-l]) return false;
        }
        return true;
    }
}
